package com.yan.programercode.chapter_1.question_1;

import java.util.Stack;

/**
 * 题目：
 * 实现一个特殊功能的栈，在实现栈的基本功能基础上，再实现返回栈中最小元素的操作
 * 要求：
 * 1、pop、push、getMin操作的时间复杂度都是O(1)
 * 2、设计的栈类型可以使用线程的栈结构
 * 
 * 方案一：
 * 只有要处理的值比stackMin栈顶的值小或者相等的时候，才向stackMin中压入
 * 弹出数据的时候，也是判断下弹出的值和stackMin中栈顶的值比较，如果相等，stackMin也需要弹出
 * 
 * @author Yan
 *
 */
public class MyStack1 {

	private Stack<Integer> stackData;
	private Stack<Integer> stackMin;
	
	public MyStack1() {
		stackData = new Stack<Integer>();
		stackMin = new Stack<Integer>();
	}
	
	public void push(int newNum){
		if(this.stackMin.isEmpty()){
			this.stackMin.push(newNum);
		}else if (newNum <= this.stackMin.peek()) {
			// 如果要操作的值和stackMin栈顶的值相同，也需要压入栈中，因为在pop操作的时候需要处理弹出的数据是最小值的情况
			this.stackMin.push(newNum);
		}
		this.stackData.push(newNum);
	}
	
	public int pop(){
		if(this.stackData.isEmpty()){
			throw new RuntimeException("Your stack is empty.");
		}
		int value = this.stackData.pop();
		// 弹出数据的时候，如果弹出的是最小值，那么stackMin中的栈顶数据也需要弹出
		// 并且，如果相同的最小值数据有多个，也都需要压入栈中
		if(value == this.getMin()){
			this.stackMin.pop();
		}
		return value;
	}
	
	public int getMin(){
		if(this.stackMin.isEmpty()){
			throw new RuntimeException("Your stack is empty.");
		}
		return this.stackMin.peek();
	}
}
